import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test3 {
    public int LIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] > list.get(list.size() - 1)) {
                list.add(nums[i]);
                continue;
            }else {
                int index = find(list,nums[i]);
                list.set(index,nums[i]);
            }
        }
        return list.size();
    }

    private int find(List<Integer> list,int target) {
        int left = 0, right = list.size(), mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        Test3 test = new Test3();
        int[] a = {1, 4, 7, 5, 6};
        System.out.println(test.LIS(a));
    }
}
